// https://leetcode.cn/problems/partition-equal-subset-sum/description/

// 算法思路总结：
// 1. 动态规划解决分割等和子集问题（0-1背包变体）
// 2. 问题转化为：是否存在子集和等于总和的一半
// 3. 状态定义：dp[i][j]表示前i个数字能否凑出和j
// 4. 状态转移：不选当前数 或 选当前数（满足容量条件）
// 5. 奇数总和直接返回false，无法平分
// 6. 时间复杂度：O(n×target)，空间复杂度：O(n×target)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <numeric>
#include <cstring>

class Solution 
{
public:
    bool dp[201][10010];

    bool canPartition(vector<int>& nums) 
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) return false;

        int target = sum / 2, m = nums.size();
        memset(dp, 0, sizeof(dp));
        dp[0][0] = true;

        for (int i = 1 ; i <= m ; i++)
        {
            for (int j = 1 ; j <= target ; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j - nums[i - 1] >= 0)
                {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }

        return dp[m][target];
    }
};

int main()
{
    vector<int> nums1 = {1,5,11,5}, nums2 = {1,2,3,5};
    Solution sol;

    cout << (sol.canPartition(nums1) == 1 ? "true" : "false") << endl;
    cout << (sol.canPartition(nums2) == 1 ? "true" : "false") << endl;

    return 0;
}